package MyDP;

/**
 * 1277. 统计全为 1 的正方形子矩阵
 *
 * 给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
 */

/**
 *     1 1 1        1 1 1
 *     1 1 1   ==>  1 2 2
 *     1 1 1        1 2 3   刚好加上dp[i][j] 就是面积了
 */
public class Leetcode1227 {
    public int countSquares(int[][] matrix) {
        if(matrix == null || matrix.length <= 0 || matrix[0].length <= 0){
            return 0;
        }

        int[][] dp = new int[matrix.length][matrix[0].length];
        int maxx = 0;
        for(int i=0; i<matrix.length; i++){
            for(int j=0; j<matrix[0].length; j++){
                if(i==0 || j==0){
                    dp[i][j] = matrix[i][j] ;
                }else{
                    if(matrix[i][j] == 1){
                        dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i][j-1]), dp[i-1][j]) + 1;
                    }
                }
                maxx += dp[i][j];
            }
        }
        return maxx;
    }
}
